# 2025.09.18力扣网刷题
# 种花问题——贪心、数组——简单
# 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
# 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
# 示例 1：
# 输入：flowerbed = [1, 0, 0, 0, 1], n = 1
# 输出：true
# 示例 2：
# 输入：flowerbed = [1, 0, 0, 0, 1], n = 2
# 输出：false
# 提示：
# 1 <= flowerbed.length <= 2 * 10^4
# flowerbed[i] 为 0 或 1
# flowerbed 中不存在相邻的两朵花
# 0 <= n <= flowerbed.length

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        def Plant(flowerbed, flowerbedSize, begin, flag, n):
            i = begin + 2 * flag
            while 0 <= i < flowerbedSize and n:
                if flowerbed[i] or (i >= 1 and flowerbed[i -  1]) or (i < flowerbedSize - 1 and flowerbed[i + 1]):
                    i += flag
                    continue
                flowerbed[i] = 1
                n -= 1
                i += flag
            return n
        length = len(flowerbed)
        begin = 0
        for i in range(length):
            if flowerbed[i]:
                begin = i
                break
        if flowerbed[begin] == 0 and n:
            flowerbed[begin] = 1
            n -= 1
        n = Plant(flowerbed, length, begin, -1, n)
        n = Plant(flowerbed, length, begin, 1, n)
        return n == 0